Reconstruct original digits from English

Time: O(N); Space: O(1); medium

Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Constraints:

  • Input contains only lowercase English letters.

  • Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as “abc” or “zerone” are not permitted.

  • Input length is less than 50,000.

Example 1:

Input: s = “owoztneoer”

Output: “012”

Example 2:

Input: s = “fviefuro”

Output: “45”

[1]:

from collections import Counter

class Solution1(object):
    def originalDigits(self, s) -> str:
        """
        :type s: str
        :rtype: str
        """
        # The count of each char in each number string.
        cnts = [Counter(_) for _ in ["zero", "one", "two", "three", \
                                     "four", "five", "six", "seven", \
                                     "eight", "nine"]]
        # cnts = [Counter({'z': 1, 'e': 1, 'r': 1, 'o': 1})
        # . . .
        # Counter({'n': 2, 'i': 1, 'e': 1})]

        # The order for greedy method
        order = [0, 2, 4, 6, 8, 1, 3, 5, 7, 9]
        # The unique char in the order.
        unique_chars = ['z', 'o', 'w', 't', 'u', \
                        'f', 'x', 's', 'g', 'n']

        cnt = Counter(list(s))   # Counter({'o': 3, 'e': 2, 'w': 1, 'z': 1, 't': 1, 'n': 1, 'r': 1})
        res = []
        for i in order:
            while cnt[unique_chars[i]] > 0:
                cnt -= cnts[i]
                res.append(i)
        res.sort()
        return "".join(map(str, res))

[4]:

sol = Solution1()
s = 'owoztneoer'
assert sol.originalDigits(s) == '012'
s = 'fviefuro'
assert sol.originalDigits(s) == '45'